1
2
3
4
5
6
7 package io.vavr.collection;
8
9 import io.vavr.*;
10 import io.vavr.control.Option;
11 import org.assertj.core.api.Assertions;
12 import org.assertj.core.api.IterableAssert;
13 import org.assertj.core.api.ObjectAssert;
14 import org.junit.Ignore;
15 import org.junit.Test;
16
17 import java.io.InvalidObjectException;
18 import java.math.BigDecimal;
19 import java.util.ArrayList;
20 import java.util.NoSuchElementException;
21 import java.util.Objects;
22 import java.util.Spliterator;
23 import java.util.concurrent.atomic.AtomicInteger;
24 import java.util.function.Function;
25 import java.util.function.Supplier;
26 import java.util.stream.Collector;
27
28
29
30
31 public class TreeTest extends AbstractTraversableTest {
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 private final Tree<Integer> tree = $(1, $(2, $(4, $(7)), $(5)), $(3, $(6, $(8), $(9))));
47
48 @Override
49 protected <T> IterableAssert<T> assertThat(Iterable<T> actual) {
50 return new IterableAssert<T>(actual) {
51 @SuppressWarnings("unchecked")
52 @Override
53 public IterableAssert<T> isEqualTo(Object expected) {
54 if (actual instanceof Option) {
55 final Option<?> opt1 = ((Option<?>) actual);
56 final Option<?> opt2 = (Option<?>) expected;
57 Assertions.assertThat(convOption(opt1)).isEqualTo(convOption(opt2));
58 } else if (expected instanceof Map) {
59 final Map<?, ?> map1 = (Map<?, ?>) actual;
60 final Map<?, ?> map2 = (Map<?, ?>) expected;
61 Assertions.assertThat(convMap(map1)).isEqualTo(convMap(map2));
62 } else if (expected instanceof Tree) {
63 assertThat(Stream.ofAll(actual)).isEqualTo(Stream.ofAll((Tree<?>) expected));
64 } else {
65 Assertions.assertThat(actual).isEqualTo((Iterable<T>) expected);
66 }
67 return this;
68 }
69
70 private Option<?> convOption(Option<?> option) {
71 return option.map(o -> (o instanceof Iterable) ? Stream.ofAll((Iterable<?>) o) : o);
72 }
73
74 private Map<?, ?> convMap(Map<?, ?> map) {
75 return map.map((k, v) -> Tuple.of(k, v instanceof Iterable ? Stream.ofAll((Iterable<?>) v) : v));
76 }
77 };
78 }
79
80 @Override
81 protected <T> ObjectAssert<T> assertThat(T actual) {
82 return new ObjectAssert<T>(actual) {
83 @Override
84 public ObjectAssert<T> isEqualTo(Object expected) {
85 if (actual instanceof Tuple2) {
86 final Tuple2<?, ?> t1 = (Tuple2<?, ?>) actual;
87 final Tuple2<?, ?> t2 = (Tuple2<?, ?>) expected;
88 assertThat((Iterable<?>) t1._1).isEqualTo(t2._1);
89 assertThat((Iterable<?>) t1._2).isEqualTo(t2._2);
90 return this;
91 } else {
92 return super.isEqualTo(expected);
93 }
94 }
95 };
96 }
97
98 @Override
99 protected <T> Collector<T, ArrayList<T>, Tree<T>> collector() {
100 return Tree.collector();
101 }
102
103 @Override
104 protected <T> Tree<T> empty() {
105 return Tree.empty();
106 }
107
108 @Override
109 protected <T> Tree.Node<T> of(T element) {
110 return Tree.of(element);
111 }
112
113 @SuppressWarnings("varargs")
114 @SafeVarargs
115 @Override
116 protected final <T> Tree<T> of(T... elements) {
117 return Tree.ofAll(List.of(elements));
118 }
119
120 @Override
121 protected <T> Tree<T> ofAll(Iterable<? extends T> elements) {
122 return Tree.ofAll(elements);
123 }
124
125 @Override
126 protected <T extends Comparable<? super T>> Tree<T> ofJavaStream(java.util.stream.Stream<? extends T> javaStream) {
127 return Tree.ofAll(javaStream);
128 }
129
130 @Override
131 protected Tree<Boolean> ofAll(boolean... elements) {
132 return Tree.ofAll(List.ofAll(elements));
133 }
134
135 @Override
136 protected Tree<Byte> ofAll(byte... elements) {
137 return Tree.ofAll(List.ofAll(elements));
138 }
139
140 @Override
141 protected Tree<Character> ofAll(char... elements) {
142 return Tree.ofAll(List.ofAll(elements));
143 }
144
145 @Override
146 protected Tree<Double> ofAll(double... elements) {
147 return Tree.ofAll(List.ofAll(elements));
148 }
149
150 @Override
151 protected Tree<Float> ofAll(float... elements) {
152 return Tree.ofAll(List.ofAll(elements));
153 }
154
155 @Override
156 protected Tree<Integer> ofAll(int... elements) {
157 return Tree.ofAll(List.ofAll(elements));
158 }
159
160 @Override
161 protected Tree<Long> ofAll(long... elements) {
162 return Tree.ofAll(List.ofAll(elements));
163 }
164
165 @Override
166 protected Tree<Short> ofAll(short... elements) {
167 return Tree.ofAll(List.ofAll(elements));
168 }
169
170 @Override
171 protected <T> Tree<T> tabulate(int n, Function<? super Integer, ? extends T> f) {
172 return Tree.tabulate(n, f);
173 }
174
175 @Override
176 protected <T> Tree<T> fill(int n, Supplier<? extends T> s) {
177 return Tree.fill(n, s);
178 }
179
180 @Override
181 protected boolean useIsEqualToInsteadOfIsSameAs() {
182 return true;
183 }
184
185 @Override
186 protected int getPeekNonNilPerformingAnAction() {
187 return 1;
188 }
189
190 @SuppressWarnings("varargs")
191 @SafeVarargs
192 protected final <T> Tree.Node<T> $(T value, Tree.Node<T>... children) {
193 return Tree.of(value, children);
194 }
195
196
197
198 @Test
199 public void shouldNarrowTree() {
200 final Tree<Double> doubles = of(1.0d);
201 final Tree<Number> numbers = Tree.narrow(doubles);
202 final boolean actual = numbers.contains(new BigDecimal("2.0"));
203 assertThat(actual).isFalse();
204 }
205
206
207
208 @Test
209 public void shouldInstantiateTreeBranchWithOf() {
210 final Tree<Integer> actual = Tree.of(1, Tree.of(2), Tree.of(3));
211 final Tree<Integer> expected = new Tree.Node<>(1, List.of(new Tree.Node<>(2, List.empty()), new Tree.Node<>(3, List.empty())));
212 assertThat(actual).isEqualTo(expected);
213 }
214
215
216
217 @Test
218 public void shouldInstantiateTreeLeafWithOf() {
219 final Tree<Integer> actual = Tree.of(1);
220 final Tree<Integer> expected = new Tree.Node<>(1, List.empty());
221 assertThat(actual).isEqualTo(expected);
222 }
223
224
225
226 @Test
227 public void shouldCreateANodeWithoutChildren() {
228 new Tree.Node<>(1, List.empty());
229 }
230
231 @Test(expected = InvalidObjectException.class)
232 public void shouldNotCallReadObjectOnNodeInstance() throws Throwable {
233 Serializables.callReadObject(tree);
234 }
235
236
237
238 @Test(expected = UnsupportedOperationException.class)
239 public void shouldNotGetValueOfNil() {
240 Tree.empty().getValue();
241 }
242
243 @Test
244 public void shouldNotGetValueOfNonNil() {
245 assertThat(tree.get()).isEqualTo(1);
246 }
247
248
249
250 @Test
251 public void shouldCalculateSizeOfALeaf() {
252 assertThat($(0).size()).isEqualTo(1);
253 }
254
255 @Test
256 public void shouldCalculateSizeOfNestedNodes() {
257 assertThat(tree.size()).isEqualTo(9);
258 }
259
260
261
262 @Test
263 public void shouldIdentifyNilAsEmpty() {
264 assertThat(Tree.empty().isEmpty()).isTrue();
265 }
266
267 @Test
268 public void shouldIdentifyNonNilAsNotEmpty() {
269 assertThat(tree.isEmpty()).isFalse();
270 }
271
272
273
274 @Test
275 public void shouldIdentifyLeafAsLeaf() {
276 assertThat($(0).isLeaf()).isTrue();
277 }
278
279 @Test
280 public void shouldIdentifyNonLeafAsNonLeaf() {
281 assertThat(tree.isLeaf()).isFalse();
282 }
283
284 @Test
285 public void shouldIdentifyNilAsNonLeaf() {
286 assertThat(Tree.empty().isLeaf()).isFalse();
287 }
288
289
290
291 @Test
292 public void shouldIdentifyLeafAsNonBranch() {
293 assertThat($(0).isBranch()).isFalse();
294 }
295
296 @Test
297 public void shouldIdentifyNonLeafAsBranch() {
298 assertThat(tree.isBranch()).isTrue();
299 }
300
301 @Test
302 public void shouldIdentifyNilAsNonBranch() {
303 assertThat(Tree.empty().isBranch()).isFalse();
304 }
305
306
307
308 @Test
309 public void shouldGetChildrenOfLeaf() {
310 assertThat($(0).getChildren()).isEqualTo(List.empty());
311 }
312
313 @Test
314 public void shouldGetChildrenOfBranch() {
315 final List<? extends Tree<Integer>> children = tree.getChildren();
316 assertThat(children.length()).isEqualTo(2);
317 assertThat(children.get(0).toLispString()).isEqualTo("(2 (4 7) 5)");
318 assertThat(children.get(1).toLispString()).isEqualTo("(3 (6 8 9))");
319 }
320
321 @Test
322 public void shouldIGetChildrenOfNil() {
323 assertThat(Tree.empty().getChildren()).isEqualTo(List.empty());
324 }
325
326
327
328 @Test
329 public void shouldCountBranchesOfNil() {
330 assertThat(Tree.empty().branchCount()).isEqualTo(0);
331 }
332
333 @Test
334 public void shouldCountBranchesOfNonNil() {
335 assertThat(tree.branchCount()).isEqualTo(5);
336 }
337
338
339
340 @Test
341 public void shouldCountLeavesOfNil() {
342 assertThat(Tree.empty().leafCount()).isEqualTo(0);
343 }
344
345 @Test
346 public void shouldCountLeavesOfNonNil() {
347 assertThat(tree.leafCount()).isEqualTo(4);
348 }
349
350
351
352 @Test
353 public void shouldCountNodesOfNil() {
354 assertThat(Tree.empty().nodeCount()).isEqualTo(0);
355 }
356
357 @Test
358 public void shouldCountNodesOfNonNil() {
359 assertThat(tree.nodeCount()).isEqualTo(9);
360 }
361
362
363
364 @Test
365 public void shouldNotFindNodeInNil() {
366 assertThat(Tree.empty().contains(1)).isFalse();
367 }
368
369 @Test
370 public void shouldFindExistingNodeInNonNil() {
371 assertThat(tree.contains(5)).isTrue();
372 }
373
374 @Test
375 public void shouldNotFindNonExistingNodeInNonNil() {
376 assertThat(tree.contains(0)).isFalse();
377 }
378
379
380
381 @Test
382 public void shouldFlatMapEmptyTree() {
383 assertThat(Tree.empty().flatMap(t -> Tree.of(1))).isEqualTo(Tree.empty());
384 }
385
386 @Test
387 public void shouldFlatMapNonEmptyTree() {
388 final Tree.Node<Integer> testee = $(1, $(2), $(3));
389 final Tree<Integer> actual = testee.flatMap(i -> $(i, $(i), $(i)));
390 final Tree<Integer> expected = $(1, $(1), $(1), $(2, $(2), $(2)), $(3, $(3), $(3)));
391 assertThat(actual).isEqualTo(expected);
392 }
393
394 @Test
395 public void shouldFlatMapNonEmptyByExpandingElements() {
396 assertThat(of(1, 2, 3).flatMap(i -> {
397 if (i == 1) {
398 return of(1, 2, 3);
399 } else if (i == 2) {
400 return of(4, 5);
401 } else {
402 return of(6);
403 }
404 })).isEqualTo($(1, $(2), $(3), $(4, $(5)), $(6)));
405 }
406
407 @Test
408 public void shouldFlatMapNonEmptyInTheRightOrder() {
409 final AtomicInteger seq = new AtomicInteger(0);
410 final Tree<Integer> actualInts = $(0, $(1), $(2))
411 .flatMap(ignored -> of(seq.getAndIncrement(), seq.getAndIncrement()));
412 final Tree<Integer> expectedInts = $(0, $(1), $(2, $(3)), $(4, $(5)));
413 assertThat(actualInts).isEqualTo(expectedInts);
414 }
415
416
417
418 @Override
419 @Test
420 public void shouldNotHasNextWhenNilIterator() {
421 assertThat(Tree.empty().iterator().hasNext()).isFalse();
422 }
423
424 @Override
425 @Test(expected = NoSuchElementException.class)
426 public void shouldThrowOnNextWhenNilIterator() {
427 Tree.empty().iterator().next();
428 }
429
430 @Override
431 @Test
432 public void shouldIterateFirstElementOfNonNil() {
433 assertThat(tree.iterator().next()).isEqualTo(1);
434 }
435
436 @Override
437 @Test
438 public void shouldFullyIterateNonNil() {
439 final int length = List
440 .of(1, 2, 4, 7, 5, 3, 6, 8, 9)
441 .zip(tree)
442 .filter(t -> Objects.equals(t._1, t._2))
443 .length();
444 assertThat(length).isEqualTo(9);
445 }
446
447
448
449 @Test
450 public void shouldMapEmpty() {
451 assertThat(Tree.empty().map(i -> i)).isEqualTo(Tree.empty());
452 }
453
454 @Test
455 public void shouldMapTree() {
456 assertThat(tree.map(i -> (char) (i + 64)).toLispString()).isEqualTo("(A (B (D G) E) (C (F H I)))");
457 }
458
459
460
461 @Test
462 public void shouldReplaceNullInEmpty() {
463 assertThat(Tree.empty().replace(null, null)).isEmpty();
464 }
465
466 @Test
467 public void shouldReplaceFirstOccurrenceUsingDepthFirstSearchInNonEmptyTree() {
468
469
470
471 final Tree<Integer> testee = Tree.of(1, Tree.of(2), Tree.of(3));
472 final Tree<Integer> actual = testee.replace(2, 99);
473 final Tree<Integer> expected = Tree.of(1, Tree.of(99), Tree.of(3));
474 assertThat(actual).isEqualTo(expected);
475 }
476
477 @Test
478 public void shouldNotReplaceAnyElementIfThereIsNoOccurrenceInNonEmptyTree() {
479 final Tree<Integer> testee = Tree.of(1, Tree.of(2), Tree.of(3));
480 final Tree<Integer> actual = testee.replace(4, 99);
481 assertThat(actual).isEqualTo(testee);
482 }
483
484
485
486 @Test
487 public void shouldTraverseValuesOfEmptyTree() {
488 assertThat(Tree.empty().values()).isEqualTo(empty());
489 }
490
491
492
493 @Test
494 public void shouldTraverseValuesUsingPreOrder() {
495 assertThat(tree.values(Tree.Order.PRE_ORDER)).isEqualTo(Stream.of(1, 2, 4, 7, 5, 3, 6, 8, 9));
496 }
497
498 @Test
499 public void shouldTraverseValuesUsingInOrder() {
500 assertThat(tree.values(Tree.Order.IN_ORDER)).isEqualTo(Stream.of(7, 4, 2, 5, 1, 8, 6, 9, 3));
501 }
502
503 @Test
504 public void shouldTraverseValuesUsingPostOrder() {
505 assertThat(tree.values(Tree.Order.POST_ORDER)).isEqualTo(Stream.of(7, 4, 5, 2, 8, 9, 6, 3, 1));
506 }
507
508 @Test
509 public void shouldTraverseValuesUsingLevelOrder() {
510 assertThat(tree.values(Tree.Order.LEVEL_ORDER)).isEqualTo(Stream.of(1, 2, 3, 4, 5, 6, 7, 8, 9));
511 }
512
513
514
515 @Test
516 public void shouldUnzipEmptyTree() {
517 assertThat(Tree.empty().unzip(t -> Tuple.of(t, t))).isEqualTo(Tuple.of(Tree.empty(), Tree.empty()));
518 }
519
520 @Test
521 public void shouldUnzipNonEmptyTree() {
522 final Tree<Integer> testee = $(1, $(2), $(3));
523 final Tuple2<Tree<Integer>, Tree<Integer>> actual = testee.unzip(i -> Tuple.of(i, -i));
524 final Tuple2<Tree<Integer>, Tree<Integer>> expected = Tuple.of($(1, $(2), $(3)), $(-1, $(-2), $(-3)));
525 assertThat(actual).isEqualTo(expected);
526 }
527
528 @Test
529 public void shouldUnzip3EmptyTree() {
530 assertThat(Tree.empty().unzip3(t -> Tuple.of(t, t, t))).isEqualTo(Tuple.of(Tree.empty(), Tree.empty(), Tree.empty()));
531 }
532
533 @Test
534 public void shouldUnzip3NonEmptyTree() {
535 final Tree<Integer> testee = $(1, $(2), $(3));
536 final Tuple3<Tree<Integer>, Tree<Integer>, Tree<Integer>> actual = testee.unzip3(i -> Tuple.of(i, -i, -i - 1));
537 final Tuple3<Tree<Integer>, Tree<Integer>, Tree<Integer>> expected = Tuple.of($(1, $(2), $(3)), $(-1, $(-2), $(-3)), $(-2, $(-3), $(-4)));
538 assertThat(actual).isEqualTo(expected);
539 }
540
541
542
543 @SuppressWarnings("EqualsWithItself")
544 @Test
545 public void shouldBeAwareThatTwoTreesOfSameInstanceAreEqual() {
546
547 assertThat(Tree.empty().equals(Tree.empty())).isTrue();
548 }
549
550 @Test
551 public void shouldBeAwareOfTwoDifferentEqualTrees() {
552 assertThat($(0).equals($(0))).isTrue();
553 }
554
555 @Test
556 public void shouldBeAwareThatTreeNotEqualsObject() {
557 assertThat($(0)).isNotEqualTo(new Object());
558 }
559
560
561
562 @Test
563 public void shouldBeAwareThatHashCodeOfEmptyIsOne() {
564 assertThat(Tree.empty().hashCode()).isEqualTo(1);
565 }
566
567 @Test
568 public void shouldBeAwareThatHashCodeOfLeafIsGreaterThanOne() {
569 assertThat($(0).hashCode()).isGreaterThan(1);
570 }
571
572
573
574 @Test
575 public void shouldTransform() {
576 final String transformed = $(42, $(2), $(3)).transform(v -> String.valueOf(v.get()));
577 assertThat(transformed).isEqualTo("42");
578 }
579
580
581
582 @Test
583 public void shouldReturnStringRepresentationOfEmpty() {
584 assertThat(Tree.empty().toString()).isEqualTo("Tree()");
585 }
586
587 @Test
588 public void shouldReturnLispStringRepresentationOfNode() {
589 assertThat(tree.toString()).isEqualTo("Tree(1, 2, 4, 7, 5, 3, 6, 8, 9)");
590 }
591
592
593
594 @Test
595 public void shouldConvertEmptyToLispString() {
596 assertThat(Tree.empty().toLispString()).isEqualTo("()");
597 }
598
599 @Test
600 public void shouldConvertNonEmptyToLispString() {
601 assertThat(tree.toLispString()).isEqualTo("(1 (2 (4 7) 5) (3 (6 8 9)))");
602 }
603
604
605
606 @Test
607 public void shouldReturnDrawStringOfEmpty() {
608 assertThat(Tree.empty().draw()).isEqualTo("▣");
609 }
610
611 @Test
612 public void shouldReturnDrawStringOfNode() {
613 assertThat(tree.draw()).isEqualTo("1\n" +
614 "├──2\n" +
615 "│ ├──4\n" +
616 "│ │ └──7\n" +
617 "│ └──5\n" +
618 "└──3\n" +
619 " └──6\n" +
620 " ├──8\n" +
621 " └──9");
622 }
623
624
625
626 @Test
627 public void shouldSerializeDeserializeComplexTree() {
628 final Object actual = Serializables.deserialize(Serializables.serialize(tree));
629 assertThat(actual).isEqualTo(tree);
630 }
631
632
633
634 @Test
635 public void shouldReturnSelfOnConvertToTree() {
636 final Value<Integer> value = of(1, 2, 3);
637 assertThat(value.toTree()).isSameAs(value);
638 }
639
640
641
642
643
644 @Ignore
645 @Override
646 @Test
647 public void shouldReturnSameInstanceWhenDistinctByComparatorEmptyTraversable() {
648
649 }
650
651
652
653 @Ignore
654 @Override
655 @Test
656 public void shouldReturnSameInstanceWhenDistinctByFunctionEmptyTraversable() {
657
658 }
659
660
661
662 @Ignore
663 @Override
664 @Test
665 public void shouldReturnSameInstanceWhenDropZeroCount() {
666
667 }
668
669 @Ignore
670 @Override
671 @Test
672 public void shouldReturnSameInstanceWhenDropNegativeCount() {
673
674 }
675
676 @Ignore
677 @Override
678 @Test
679 public void shouldReturnSameInstanceWhenEmptyDropOne() {
680
681 }
682
683
684
685 @Ignore
686 @Override
687 @Test
688 public void shouldReturnSameInstanceWhenDropRightZeroCount() {
689
690 }
691
692 @Ignore
693 @Override
694 @Test
695 public void shouldReturnSameInstanceWhenDropRightNegativeCount() {
696
697 }
698
699 @Ignore
700 @Override
701 @Test
702 public void shouldReturnSameInstanceWhenEmptyDropRightOne() {
703
704 }
705
706
707
708 @Ignore
709 @Override
710 @Test
711 public void shouldReturnSameInstanceWhenEmptyDropUntil() {
712
713 }
714
715
716
717 @Ignore
718 @Override
719 @Test
720 public void shouldReturnSameInstanceWhenEmptyDropWhile() {
721
722 }
723
724
725
726 @Ignore
727 @Override
728 @Test
729 public void shouldReturnSameInstanceWhenFilteringEmptyTraversable() {
730
731 }
732
733
734
735 @Ignore
736 @Override
737 @Test
738 public void shouldReturnSameInstanceIfTakeAll() {
739
740 }
741
742
743
744 @Ignore
745 @Override
746 @Test
747 public void shouldReturnSameInstanceIfTakeRightAll() {
748
749 }
750
751
752
753 @Ignore
754 @Override
755 @Test
756 public void shouldReturnSameInstanceWhenEmptyTakeUntil() {
757
758 }
759
760
761
762 @Ignore
763 @Override
764 @Test
765 public void shouldReturnSameInstanceWhenEmptyTakeWhile() {
766
767 }
768
769
770
771 @Test
772 public void shouldHaveOrderedSpliterator() {
773 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.ORDERED)).isTrue();
774 }
775
776 @Test
777 public void shouldNotHaveSortedSpliterator() {
778 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.SORTED)).isFalse();
779 }
780
781 @Test
782 public void shouldHaveSizedSpliterator() {
783 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.SIZED | Spliterator.SUBSIZED)).isTrue();
784 }
785
786 @Test
787 public void shouldNotHaveDistinctSpliterator() {
788 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.DISTINCT)).isFalse();
789 }
790
791 @Test
792 public void shouldReturnSizeWhenSpliterator() {
793 assertThat(of(1, 2, 3).spliterator().getExactSizeIfKnown()).isEqualTo(3);
794 }
795
796
797
798 @Test
799 public void shouldReturnTrueWhenIsSequentialCalled() {
800 assertThat(of(1, 2, 3).isSequential()).isTrue();
801 }
802
803 }